{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum AND Sum of Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumANDSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组的最大与和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为&nbsp;<code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>numSlots</code>&nbsp;，满足<code>2 * numSlots &gt;= n</code>&nbsp;。总共有&nbsp;<code>numSlots</code>&nbsp;个篮子，编号为&nbsp;<code>1</code>&nbsp;到&nbsp;<code>numSlots</code>&nbsp;。</p>\n",
    "\n",
    "<p>你需要把所有&nbsp;<code>n</code>&nbsp;个整数分到这些篮子中，且每个篮子 <strong>至多</strong>&nbsp;有 2 个整数。一种分配方案的 <strong>与和</strong>&nbsp;定义为每个数与它所在篮子编号的 <strong>按位与运算</strong>&nbsp;结果之和。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，将数字&nbsp;<code>[1, 3]</code>&nbsp;放入篮子&nbsp;<strong><em><code>1</code></em></strong>&nbsp;中，<code>[4, 6]</code> 放入篮子&nbsp;<strong><em><code>2</code></em></strong>&nbsp;中，这个方案的与和为&nbsp;<code>(1 AND <strong><em>1</em></strong>) + (3 AND <strong><em>1</em></strong>) + (4 AND <em><strong>2</strong></em>) + (6 AND <em><strong>2</strong></em>) = 1 + 1 + 0 + 2 = 4</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回将 <code>nums</code>&nbsp;中所有数放入<em>&nbsp;</em><code>numSlots</code>&nbsp;个篮子中的最大与和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,3,4,5,6], numSlots = 3\n",
    "<b>输出：</b>9\n",
    "<b>解释：</b>一个可行的方案是 [1, 4] 放入篮子 <em><strong>1</strong></em>&nbsp;中，[2, 6] 放入篮子 <strong><em>2</em></strong>&nbsp;中，[3, 5] 放入篮子 <strong><em>3</em></strong> 中。\n",
    "最大与和为 (1 AND <strong><em>1</em></strong>) + (4 AND <strong><em>1</em></strong>) + (2 AND <strong><em>2</em></strong>) + (6 AND <strong><em>2</em></strong>) + (3 AND <strong><em>3</em></strong>) + (5 AND <em><strong>3</strong></em>) = 1 + 0 + 2 + 2 + 3 + 1 = 9 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,3,10,4,7,1], numSlots = 9\n",
    "<b>输出：</b>24\n",
    "<b>解释：</b>一个可行的方案是 [1, 1] 放入篮子 <em><strong>1</strong></em> 中，[3] 放入篮子 <em><strong>3</strong></em> 中，[4] 放入篮子 <strong><em>4</em></strong> 中，[7] 放入篮子 <strong><em>7</em></strong> 中，[10] 放入篮子 <strong><em>9</em></strong>&nbsp;中。\n",
    "最大与和为 (1 AND <strong><em>1</em></strong>) + (1 AND <strong><em>1</em></strong>) + (3 AND <strong><em>3</em></strong>) + (4 AND <strong><em>4</em></strong>) + (7 AND <strong><em>7</em></strong>) + (10 AND <strong><em>9</em></strong>) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。\n",
    "注意，篮子 2 ，5 ，6 和 8 是空的，这是允许的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= numSlots &lt;= 9</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * numSlots</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 15</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-and-sum-of-array](https://leetcode.cn/problems/maximum-and-sum-of-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-and-sum-of-array](https://leetcode.cn/problems/maximum-and-sum-of-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6]\\n3', '[1,3,10,4,7,1]\\n9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # match\n",
    "        n = len(nums)\n",
    "        mask_max = 3 ** numSlots\n",
    "\n",
    "        f = [0] * mask_max        \n",
    "        for mask in range(1, mask_max):\n",
    "            cnt, dummy = 0, mask\n",
    "\n",
    "            for i in range(numSlots):\n",
    "                cnt += dummy % 3\n",
    "                dummy //= 3\n",
    "            \n",
    "            if cnt > n:\n",
    "                continue\n",
    "            \n",
    "            dummy, w = mask, 1\n",
    "            for i in range(numSlots):\n",
    "                has = dummy % 3\n",
    "                if has > 0:\n",
    "                    f[mask] = max(f[mask], f[mask - w] + (nums[cnt - 1] & (i + 1)))\n",
    "                dummy //= 3\n",
    "                w *= 3\n",
    "        \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "#         f = [0] * (1 << (numSlots * 2))\n",
    "#         for i, fi in enumerate(f):\n",
    "#             # print (i,fi)\n",
    "#             c = i.bit_count()\n",
    "#             # print(c)\n",
    "#             if c >= len(nums): continue\n",
    "#             for j in range(numSlots * 2):\n",
    "#                 if (i & (1 << j)) == 0:  # 枚举空篮子 j\n",
    "#                     s = i | (1 << j)\n",
    "#                     # print (s)\n",
    "#                     f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c]))\n",
    "#         return max(f)\n",
    "from heapq import heappop, heappush\n",
    "from typing import List, Tuple\n",
    "from collections import deque\n",
    "INF = int(1e18)\n",
    "class Edge:\n",
    "    __slots__ = (\"fromV\", \"toV\", \"cap\", \"cost\", \"flow\")\n",
    "    def __init__(self, fromV: int, toV: int, cap: int, cost: int, flow: int) -> None:\n",
    "        self.fromV = fromV\n",
    "        self.toV = toV\n",
    "        self.cap = cap\n",
    "        self.cost = cost\n",
    "        self.flow = flow\n",
    "class MinCostMaxFlowEK:\n",
    "    \"\"\"最小费用流的复杂度为流量*spfa的复杂度\"\"\"\n",
    "    __slots__ = (\"_n\", \"_start\", \"_end\", \"_edges\", \"_reGraph\", \"_dist\", \"_pre\", \"_flow\")\n",
    "    def __init__(self, n: int, start: int, end: int):\n",
    "        \"\"\"\n",
    "        Args:\n",
    "            n (int): 包含虚拟点在内的总点数\n",
    "            start (int): (虚拟)源点\n",
    "            end (int): (虚拟)汇点\n",
    "        \"\"\"\n",
    "        assert 0 <= start < n and 0 <= end < n\n",
    "        self._n = n\n",
    "        self._start = start\n",
    "        self._end = end\n",
    "        self._edges: List[\"Edge\"] = []\n",
    "        self._reGraph: List[List[int]] = [[] for _ in range(n)]  # 残量图存储的是边的下标\n",
    "\n",
    "        self._dist = [INF] * n\n",
    "        self._flow = [0] * n\n",
    "        self._pre = [-1] * n\n",
    "    def addEdge(self, fromV: int, toV: int, cap: int, cost: int) -> None:\n",
    "        \"\"\"原边索引为i 反向边索引为i^1\"\"\"\n",
    "        self._edges.append(Edge(fromV, toV, cap, cost, 0))\n",
    "        self._edges.append(Edge(toV, fromV, 0, -cost, 0))\n",
    "        len_ = len(self._edges)\n",
    "        self._reGraph[fromV].append(len_ - 2)\n",
    "        self._reGraph[toV].append(len_ - 1)\n",
    "    def work(self) -> Tuple[int, int]:\n",
    "        \"\"\"\n",
    "        Returns:\n",
    "            Tuple[int, int]: [最大流,最小费用]\n",
    "        \"\"\"\n",
    "        maxFlow, minCost = 0, 0\n",
    "        while self._spfa():\n",
    "            delta = self._flow[self._end]\n",
    "            minCost += delta * self._dist[self._end]\n",
    "            maxFlow += delta\n",
    "            cur = self._end\n",
    "            while cur != self._start:\n",
    "                edgeIndex = self._pre[cur]\n",
    "                self._edges[edgeIndex].flow += delta\n",
    "                self._edges[edgeIndex ^ 1].flow -= delta\n",
    "                cur = self._edges[edgeIndex].fromV\n",
    "        return maxFlow, minCost\n",
    "    def _spfa(self) -> bool:\n",
    "        \"\"\"spfa沿着最短路寻找增广路径  有负cost的边不能用dijkstra\"\"\"\n",
    "        n, start, end, edges, reGraph = (\n",
    "            self._n,\n",
    "            self._start,\n",
    "            self._end,\n",
    "            self._edges,\n",
    "            self._reGraph,\n",
    "        )\n",
    "        self._flow = flow = [0] * n\n",
    "        self._pre = pre = [-1] * n\n",
    "        self._dist = dist = [INF] * n\n",
    "        dist[start] = 0\n",
    "        flow[start] = INF\n",
    "        inQueue = [False] * n\n",
    "        inQueue[start] = True\n",
    "        queue = deque([start])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            inQueue[cur] = False\n",
    "            for edgeIndex in reGraph[cur]:\n",
    "                edge = edges[edgeIndex]\n",
    "                cost, remain, next = edge.cost, edge.cap - edge.flow, edge.toV\n",
    "                if remain > 0 and dist[cur] + cost < dist[next]:\n",
    "                    dist[next] = dist[cur] + cost\n",
    "                    pre[next] = edgeIndex\n",
    "                    flow[next] = remain if remain < flow[cur] else flow[cur]\n",
    "                    if not inQueue[next]:\n",
    "                        inQueue[next] = True\n",
    "                        if queue and dist[queue[0]] > dist[next]:\n",
    "                            queue.appendleft(next)\n",
    "                        else:\n",
    "                            queue.append(next)\n",
    "        return pre[end] != -1\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], m: int) -> int:\n",
    "        n=len(nums)\n",
    "        st=n+m+5\n",
    "        ed=st+1\n",
    "        mc=MinCostMaxFlowEK(n+m+10,st,ed)\n",
    "        for i in range(n):\n",
    "            mc.addEdge(st,i,1,0)\n",
    "        for i in range(n):\n",
    "            for j in range(1,m+1):\n",
    "                mc.addEdge(i,j+n,1,-(nums[i]&j))\n",
    "        for j in range(1,m+1):\n",
    "            mc.addEdge(j+n,ed,2,0)\n",
    "        return -mc.work()[1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        mask_max = 3 ** numSlots\n",
    "\n",
    "        f = [0] * mask_max        \n",
    "        for mask in range(1, mask_max):\n",
    "            cnt, dummy = 0, mask\n",
    "\n",
    "            for i in range(numSlots):\n",
    "                cnt += dummy % 3\n",
    "                dummy //= 3\n",
    "            \n",
    "            if cnt > n:\n",
    "                continue\n",
    "            \n",
    "            dummy, w = mask, 1\n",
    "            for i in range(numSlots):\n",
    "                has = dummy % 3\n",
    "                if has > 0:\n",
    "                    f[mask] = max(f[mask], f[mask - w] + (nums[cnt - 1] & (i + 1)))\n",
    "                dummy //= 3\n",
    "                w *= 3\n",
    "        \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        mask_max = 3 ** numSlots\n",
    "\n",
    "        f = [0] * mask_max        \n",
    "        for mask in range(1, mask_max):\n",
    "            cnt, dummy = 0, mask\n",
    "\n",
    "            for i in range(numSlots):\n",
    "                cnt += dummy % 3\n",
    "                dummy //= 3\n",
    "            \n",
    "            if cnt > n:\n",
    "                continue\n",
    "            \n",
    "            dummy, w = mask, 1\n",
    "            for i in range(numSlots):\n",
    "                has = dummy % 3\n",
    "                if has > 0:\n",
    "                    f[mask] = max(f[mask], f[mask - w] + (nums[cnt - 1] & (i + 1)))\n",
    "                dummy //= 3\n",
    "                w *= 3\n",
    "        \n",
    "        return max(f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        mask_max = 3 ** numSlots\n",
    "\n",
    "        f = [0] * mask_max        \n",
    "        for mask in range(1, mask_max):\n",
    "            cnt, dummy = 0, mask\n",
    "\n",
    "            for i in range(numSlots):\n",
    "                cnt += dummy % 3\n",
    "                dummy //= 3\n",
    "            \n",
    "            if cnt > n:\n",
    "                continue\n",
    "            \n",
    "            dummy, w = mask, 1\n",
    "            for i in range(numSlots):\n",
    "                has = dummy % 3\n",
    "                if has > 0:\n",
    "                    f[mask] = max(f[mask], f[mask - w] + (nums[cnt - 1] & (i + 1)))\n",
    "                dummy //= 3\n",
    "                w *= 3\n",
    "        \n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        case = pow(3, numSlots)\n",
    "        dp = [- float('inf')] * case\n",
    "        dp[0] = 0\n",
    "        for num in nums:\n",
    "            new = [- float('inf')] * case\n",
    "            for i in range(case):\n",
    "                f = 1 \n",
    "                mask = i \n",
    "                for j in range(numSlots):\n",
    "                    cur = mask % 3 \n",
    "                    if cur > 0:\n",
    "                        new[i] = max(new[i], dp[i - f] + ((j + 1) & num))\n",
    "                    mask //= 3\n",
    "                    f *= 3 \n",
    "            dp = new\n",
    "        # print(dp) \n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from typing import List, Tuple\n",
    "from collections import deque\n",
    "INF = int(1e18)\n",
    "class Edge:\n",
    "    __slots__ = (\"fromV\", \"toV\", \"cap\", \"cost\", \"flow\")\n",
    "    def __init__(self, fromV: int, toV: int, cap: int, cost: int, flow: int) -> None:\n",
    "        self.fromV = fromV\n",
    "        self.toV = toV\n",
    "        self.cap = cap\n",
    "        self.cost = cost\n",
    "        self.flow = flow\n",
    "class MinCostMaxFlowEK:\n",
    "    \"\"\"最小费用流的复杂度为流量*spfa的复杂度\"\"\"\n",
    "    __slots__ = (\"_n\", \"_start\", \"_end\", \"_edges\", \"_reGraph\", \"_dist\", \"_pre\", \"_flow\")\n",
    "    def __init__(self, n: int, start: int, end: int):\n",
    "        \"\"\"\n",
    "        Args:\n",
    "            n (int): 包含虚拟点在内的总点数\n",
    "            start (int): (虚拟)源点\n",
    "            end (int): (虚拟)汇点\n",
    "        \"\"\"\n",
    "        assert 0 <= start < n and 0 <= end < n\n",
    "        self._n = n\n",
    "        self._start = start\n",
    "        self._end = end\n",
    "        self._edges: List[\"Edge\"] = []\n",
    "        self._reGraph: List[List[int]] = [[] for _ in range(n)]  # 残量图存储的是边的下标\n",
    "\n",
    "        self._dist = [INF] * n\n",
    "        self._flow = [0] * n\n",
    "        self._pre = [-1] * n\n",
    "    def addEdge(self, fromV: int, toV: int, cap: int, cost: int) -> None:\n",
    "        \"\"\"原边索引为i 反向边索引为i^1\"\"\"\n",
    "        self._edges.append(Edge(fromV, toV, cap, cost, 0))\n",
    "        self._edges.append(Edge(toV, fromV, 0, -cost, 0))\n",
    "        len_ = len(self._edges)\n",
    "        self._reGraph[fromV].append(len_ - 2)\n",
    "        self._reGraph[toV].append(len_ - 1)\n",
    "    def work(self) -> Tuple[int, int]:\n",
    "        \"\"\"\n",
    "        Returns:\n",
    "            Tuple[int, int]: [最大流,最小费用]\n",
    "        \"\"\"\n",
    "        maxFlow, minCost = 0, 0\n",
    "        while self._spfa():\n",
    "            delta = self._flow[self._end]\n",
    "            minCost += delta * self._dist[self._end]\n",
    "            maxFlow += delta\n",
    "            cur = self._end\n",
    "            while cur != self._start:\n",
    "                edgeIndex = self._pre[cur]\n",
    "                self._edges[edgeIndex].flow += delta\n",
    "                self._edges[edgeIndex ^ 1].flow -= delta\n",
    "                cur = self._edges[edgeIndex].fromV\n",
    "        return maxFlow, minCost\n",
    "    def _spfa(self) -> bool:\n",
    "        \"\"\"spfa沿着最短路寻找增广路径  有负cost的边不能用dijkstra\"\"\"\n",
    "        n, start, end, edges, reGraph = (\n",
    "            self._n,\n",
    "            self._start,\n",
    "            self._end,\n",
    "            self._edges,\n",
    "            self._reGraph,\n",
    "        )\n",
    "        self._flow = flow = [0] * n\n",
    "        self._pre = pre = [-1] * n\n",
    "        self._dist = dist = [INF] * n\n",
    "        dist[start] = 0\n",
    "        flow[start] = INF\n",
    "        inQueue = [False] * n\n",
    "        inQueue[start] = True\n",
    "        queue = deque([start])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            inQueue[cur] = False\n",
    "            for edgeIndex in reGraph[cur]:\n",
    "                edge = edges[edgeIndex]\n",
    "                cost, remain, next = edge.cost, edge.cap - edge.flow, edge.toV\n",
    "                if remain > 0 and dist[cur] + cost < dist[next]:\n",
    "                    dist[next] = dist[cur] + cost\n",
    "                    pre[next] = edgeIndex\n",
    "                    flow[next] = remain if remain < flow[cur] else flow[cur]\n",
    "                    if not inQueue[next]:\n",
    "                        inQueue[next] = True\n",
    "                        if queue and dist[queue[0]] > dist[next]:\n",
    "                            queue.appendleft(next)\n",
    "                        else:\n",
    "                            queue.append(next)\n",
    "        return pre[end] != -1\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], m: int) -> int:\n",
    "        n=len(nums)\n",
    "        st=n+m+5\n",
    "        ed=st+1\n",
    "        mc=MinCostMaxFlowEK(n+m+10,st,ed)\n",
    "        for i in range(n):\n",
    "            mc.addEdge(st,i,1,0)\n",
    "        for i in range(n):\n",
    "            for j in range(1,m+1):\n",
    "                mc.addEdge(i,j+n,1,-(nums[i]&j))\n",
    "        for j in range(1,m+1):\n",
    "            mc.addEdge(j+n,ed,2,0)\n",
    "        return -mc.work()[1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        case = pow(3, numSlots)\n",
    "        dp = [- float('inf')] * case\n",
    "        dp[0] = 0\n",
    "        for num in nums:\n",
    "            new = [- float('inf')] * case\n",
    "            for i in range(case):\n",
    "                f = 1 \n",
    "                mask = i \n",
    "                for j in range(numSlots):\n",
    "                    cur = mask % 3 \n",
    "                    if cur > 0:\n",
    "                        new[i] = max(new[i], dp[i - f] + ((j + 1) & num))\n",
    "                    mask //= 3\n",
    "                    f *= 3 \n",
    "            dp = new\n",
    "        # print(dp) \n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        f = [0] * (1 << (numSlots * 2))\n",
    "        for i, fi in enumerate(f):\n",
    "            c = i.bit_count()\n",
    "            if c >= len(nums): continue\n",
    "            for j in range(numSlots * 2):\n",
    "                if (i & (1 << j)) == 0:  # 枚举空篮子 j\n",
    "                    s = i | (1 << j)\n",
    "                    f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c]))\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # f = [0] * (1 << (numSlots * 2)) # 视作有2*numSlots个篮子，每个篮子至多可以放1个整数\n",
    "        # for i, fi in enumerate(f):\n",
    "        #     c = i.bit_count()\n",
    "        #     if c >= len(nums): continue\n",
    "\n",
    "        #     for j in range(numSlots * 2):\n",
    "        #         if (i & (1 << j)) == 0: #枚举空蓝子j\n",
    "        #             s = i | (1 << j)\n",
    "        #             f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c])) # 状态转移\n",
    "        # return max(f)\n",
    "    # 最小费用最大流： 建图\n",
    "    # 集合A为数组，B为篮子；从源点连容量为1费用为0的边到a中各点，从b中各点连容量为2费用为0的边到汇点，a的每个数字nums[i]向b的每个篮子j连边，容量为正无穷，费用为-nums[i]&j\n",
    "    # 跑最小费用最大流的结果的相反数就是匹配a中所有数字的最大花费，即最大与和\n",
    "        f = [0] * (1 << (numSlots * 2)) \n",
    "        for i, fi in enumerate(f):\n",
    "            c = i.bit_count()\n",
    "            if c >= len(nums): continue\n",
    "            \n",
    "            for j in range(numSlots * 2):\n",
    "                if (i & (1 << j)) == 0:\n",
    "                    s = i | (1 << j)\n",
    "                    f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c]))\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        \n",
    "        slots = 1 << (2 * numSlots)\n",
    "        \n",
    "        dp = [0 for _ in range(slots)]\n",
    "\n",
    "        for state in range(slots):\n",
    "            c = bin(state).count('1')\n",
    "            if c > len(nums):\n",
    "                continue\n",
    "            for ii in range(numSlots * 2):\n",
    "                if (state >> ii) & 1:\n",
    "                    dp[state] = max(dp[state], dp[state ^ (1 << ii)] + (nums[c-1] & (ii//2 + 1)))\n",
    "        \n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        m = 1 << (numSlots * 2)\n",
    "        f = [0] * m\n",
    "        for i in range(m):\n",
    "            c = i.bit_count()\n",
    "            if c >= len(nums): continue\n",
    "            for j in range(numSlots * 2):\n",
    "                if ((i >> j) & 1) == 0:\n",
    "                    s = i | (1 << j)\n",
    "                    f[s] = max(f[s], f[i] + (nums[c] & (j // 2 + 1)))\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # def count_ones(n):\n",
    "        #     return sum([(n >> i) & 1 for i in range(n_slot * 2)])\n",
    "\n",
    "        n_num, n_slot = len(nums), numSlots  \n",
    "        dp = [0 for _ in range(1 << (2 * n_slot))]\n",
    "        for i_dp in range(len(dp)):\n",
    "            i_num = i_dp.bit_count()\n",
    "            if i_num >= n_num: \n",
    "                continue\n",
    "            else:\n",
    "                for i in range(2 * n_slot):\n",
    "                    if (i_dp >> i) & 1 == 0:\n",
    "                        y = i_dp | (1 << i)\n",
    "                        z = (i // 2 + 1) & nums[i_num]\n",
    "                        dp[y] = max(dp[y], dp[i_dp] + z)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        \"\"\"\n",
    "            - 最多 18 个数，每个数有放入/不放入篮子 2 种情况，总的状态数量 2^18\n",
    "            - 最多 9 个篮子，每个篮子可以放入 0/1/2 个数，总的状态数 3^9\n",
    "\n",
    "            (1) 每个篮子最多放 2 个整数。\n",
    "            (2) 看成有 2 * numSlots 个篮子，每个篮子最多放 1 个整数。\n",
    "            (3) 假设 mask 中 1 的个数为 cnt，则定义 dp[mask] 是把前 cnt 个数字放到篮子里，且放了数字的篮子集合为 i 时的最大与和。\n",
    "        \"\"\"\n",
    "        # 0000100: 第一个数放在第 3 个篮子\n",
    "        # 0001010: 前两个数放在第 2/4 个篮子\n",
    "\n",
    "        dp = [0] * (1 << (numSlots * 2))\n",
    "        for mask, x in enumerate(dp):\n",
    "            # 已经放了 x 个数字\n",
    "            cnt = mask.bit_count()\n",
    "            if cnt >= len(nums):\n",
    "                continue\n",
    "\n",
    "            # 下一个要放的数字\n",
    "            next_num = nums[cnt]\n",
    "\n",
    "            # 枚举空篮子的位置\n",
    "            for j in range(numSlots * 2):\n",
    "                # 第 j 个篮子可以放东西\n",
    "                if (mask & (1 << j)) == 0:\n",
    "                    new_mask = mask | (1 << j)\n",
    "                    dp[new_mask] = max(dp[new_mask], x + ((j//2+1) & next_num))\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        F = [0] * (2**(2*numSlots))\n",
    "        for i in range(2**(2*numSlots)):\n",
    "            c = i.bit_count()\n",
    "            if c >= n:continue\n",
    "            for x in range(2*numSlots):\n",
    "                if i >> x & 1:continue\n",
    "                F[i|1 << x] = max(F[i|1 << x],F[i] + ((x//2+1) & nums[c]))\n",
    "        return max(F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        tn=2*numSlots\n",
    "        n=len(nums)\n",
    "        dpls=[0 for i in range(1<<tn)]\n",
    "  \n",
    "        for i in range(1,1<<tn):\n",
    "            c=i.bit_count()\n",
    "            if c>n:\n",
    "                continue\n",
    "            for j in range(tn):\n",
    "                if (i>>j)&1==1:\n",
    "                    mask=i^(1<<j)\n",
    "                    dpls[i]=max(dpls[mask]+((j//2+1)&nums[c-1]),dpls[i])\n",
    "                    \n",
    "        return max(dpls)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # n = len(nums)\n",
    "        # u = (1 << n) - 1\n",
    "        # #用nums作为集合， iterate每个numSlot的index\n",
    "        # @cache\n",
    "        # def dfs(u, idx, cnt):\n",
    "        #     if cnt == 3:\n",
    "        #         return -inf\n",
    "        #     if idx == numSlots:\n",
    "        #         return 0 if u == 0 and cnt == 0 else -inf\n",
    "        #     cur = dfs(u, idx + 1, 0)\n",
    "        #     for i in range(n):\n",
    "        #         if (u >> i) & 1:\n",
    "        #             cur = max(cur, (nums[i] & (idx + 1)) + dfs(u ^ (1 << i), idx, cnt + 1), \n",
    "        #             (nums[i] & (idx + 1)) + dfs(u ^ (1 << i), idx + 1, 1))\n",
    "        #     return cur\n",
    "        # return dfs(u, 0, 0)\n",
    "\n",
    "        #反过来， 用slots作为集合， iterate每个num放哪里\n",
    "        # @cache\n",
    "        # def dfs(u, idx):\n",
    "        #     if idx == len(nums):\n",
    "        #         return 0\n",
    "        #     mask = u\n",
    "        #     ans = -inf\n",
    "        #     for i in range(numSlots):\n",
    "        #         if mask % 3 >= 1:\n",
    "        #             ans = max(ans, dfs(u - 3 ** i, idx + 1) + (nums[idx] & (i + 1)))\n",
    "        #         mask //= 3\n",
    "        #     return ans\n",
    "        # return dfs(u, 0)\n",
    "\n",
    "        # u = 3 ** numSlots\n",
    "        # n = len(nums)\n",
    "        # dp = [[0] * (n + 1) for _ in range(u)]\n",
    "        # #状态\n",
    "        # for i in range(u):\n",
    "        #     mask = i\n",
    "        #     for k in range(numSlots):\n",
    "        #         if mask % 3 < 2:\n",
    "        #             for j in range(n):\n",
    "        #                 dp[i + (3 ** k)][j + 1] = max(dp[i + (3 ** k)][j + 1], dp[i][j] + (nums[j] & (k + 1)))\n",
    "        #         mask //= 3\n",
    "        # ans = 0\n",
    "        # for i in range(u):\n",
    "        #     ans = max(ans, dp[i][n])\n",
    "        # return ans\n",
    "\n",
    "        #直接用两个分别的slot来代表一个slot\n",
    "        dp = [0] * (1 << (numSlots * 2))\n",
    "        ans = 0\n",
    "        for i, x in enumerate(dp):\n",
    "            cnt = i.bit_count()\n",
    "            if cnt >= len(nums):\n",
    "                continue\n",
    "            for j in range(numSlots * 2):\n",
    "                if (i >> j) & 1 == 0:\n",
    "                    dp[i|(1 << j)] = max(dp[i|(1 << j)], dp[i] + (nums[cnt] & (j // 2 + 1)))\n",
    "                    ans = max(ans, dp[i|(1 << j)])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n, m = len(nums), numSlots\n",
    "        f = [0] * (1 << (2 * m))\n",
    "        for i in range(1 << (2 * m)):\n",
    "            if i.bit_count() >= n:\n",
    "                continue\n",
    "            v = nums[i.bit_count()]\n",
    "            for j in range(2 * m):\n",
    "                if i >> j & 1 == 0:\n",
    "                    f[i | 1 << j] = max(f[i | 1 << j], (v & (j // 2 + 1)) + f[i])\n",
    "        return max(f)\n",
    "                    \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\r\n",
    "设 i 的二进制中的 1 的个数为 c，定义 f[i] 表示将 nums 的前 c 个数字放到篮子中，\r\n",
    "且放了数字的篮子集合为 i 时的最大与和。初始值 f[0]=0。\r\n",
    "'''\r\n",
    "class Solution:\r\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\r\n",
    "        f = [0] * (1 << (numSlots * 2))\r\n",
    "        for i, fi in enumerate(f):\r\n",
    "            c = i.bit_count()\r\n",
    "            if c >= len(nums): continue\r\n",
    "            for j in range(numSlots * 2):\r\n",
    "                if (i & (1 << j)) == 0:  # 枚举空篮子 j\r\n",
    "                    s = i | (1 << j)\r\n",
    "                    f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c]))\r\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # 1-numSlots\n",
    "        # 0 1 ... 2*numSlots-1 \n",
    "\n",
    "        # 已经将前c个以组合i的形式放入 （求得了唯一解）\n",
    "        # 现在考虑第c+1个 加入到以组合i为前提的放置中\n",
    "        n = len(nums)\n",
    "        f = [0]*(1 << 2*numSlots)\n",
    "\n",
    "        # 代码中 c 依赖 i （1的数量）\n",
    "        for i in range(1 << (2*numSlots)):\n",
    "            c = i.bit_count()\n",
    "            if c >= n:\n",
    "                continue\n",
    "            for j in range(2*numSlots):\n",
    "                if (i >> j) & 1 == 1:\n",
    "                    continue\n",
    "                s = i | (1 << j)\n",
    "                f[s] = max(f[s], f[i] + (nums[c] & (j // 2 + 1)))\n",
    "\n",
    "        return max(f)                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n, m = len(nums), numSlots * 2\n",
    "        g = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(numSlots):\n",
    "                g[i][j] = g[i][j + numSlots] = nums[i] & (j + 1)\n",
    "        f = [-inf] * (1 << m)\n",
    "        f[0] = 0\n",
    "        ans = 0\n",
    "        for mask in range(1, 1 << m):\n",
    "            c = bin(mask).count(\"1\")\n",
    "            if c > n: continue\n",
    "            for i in range(m):\n",
    "                if (mask >> i) & 1:\n",
    "                    f[mask] = max(f[mask], f[mask ^ (1 << i)] + g[c - 1][i])\n",
    "            if c == n:\n",
    "                ans = max(ans, f[mask])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        #copy\n",
    "        f = [0]*(1<<(numSlots*2))\n",
    "        for i , fi in enumerate(f):\n",
    "            c = i.bit_count()\n",
    "            if c >= len(nums):\n",
    "                continue\n",
    "            for j in range(numSlots*2):\n",
    "                if (i&(1<<j)) == 0:\n",
    "                    s= i|(1<<j)\n",
    "                    f[s] = max(f[s],f[i]+((j//2 +1)&nums[c]))\n",
    "        return max(f)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # n = len(nums)\n",
    "        # u = (1 << n) - 1\n",
    "        # #用nums作为集合， iterate每个numSlot的index\n",
    "        # @cache\n",
    "        # def dfs(u, idx, cnt):\n",
    "        #     if cnt == 3:\n",
    "        #         return -inf\n",
    "        #     if idx == numSlots:\n",
    "        #         return 0 if u == 0 and cnt == 0 else -inf\n",
    "        #     cur = dfs(u, idx + 1, 0)\n",
    "        #     for i in range(n):\n",
    "        #         if (u >> i) & 1:\n",
    "        #             cur = max(cur, (nums[i] & (idx + 1)) + dfs(u ^ (1 << i), idx, cnt + 1), \n",
    "        #             (nums[i] & (idx + 1)) + dfs(u ^ (1 << i), idx + 1, 1))\n",
    "        #     return cur\n",
    "        # return dfs(u, 0, 0)\n",
    "\n",
    "        #反过来， 用slots作为集合， iterate每个num放哪里\n",
    "        # @cache\n",
    "        # def dfs(u, idx):\n",
    "        #     if idx == len(nums):\n",
    "        #         return 0\n",
    "        #     mask = u\n",
    "        #     ans = -inf\n",
    "        #     for i in range(numSlots):\n",
    "        #         if mask % 3 >= 1:\n",
    "        #             ans = max(ans, dfs(u - 3 ** i, idx + 1) + (nums[idx] & (i + 1)))\n",
    "        #         mask //= 3\n",
    "        #     return ans\n",
    "        # return dfs(u, 0)\n",
    "\n",
    "        # u = 3 ** numSlots\n",
    "        # n = len(nums)\n",
    "        # dp = [[0] * (n + 1) for _ in range(u)]\n",
    "        # #状态\n",
    "        # for i in range(u):\n",
    "        #     mask = i\n",
    "        #     for k in range(numSlots):\n",
    "        #         if mask % 3 < 2:\n",
    "        #             for j in range(n):\n",
    "        #                 dp[i + (3 ** k)][j + 1] = max(dp[i + (3 ** k)][j + 1], dp[i][j] + (nums[j] & (k + 1)))\n",
    "        #         mask //= 3\n",
    "        # ans = 0\n",
    "        # for i in range(u):\n",
    "        #     ans = max(ans, dp[i][n])\n",
    "        # return ans\n",
    "\n",
    "        #直接用两个分别的slot来代表一个slot\n",
    "        dp = [0] * (1 << (numSlots * 2))\n",
    "        ans = 0\n",
    "        for i in range(1 << (numSlots * 2)):\n",
    "            cnt = i.bit_count()\n",
    "            if cnt >= len(nums):\n",
    "                continue\n",
    "            for j in range(numSlots * 2):\n",
    "                if (i >> j) & 1 == 0:\n",
    "                    dp[i|(1 << j)] = max(dp[i|(1 << j)], dp[i] + (nums[cnt] & (j // 2 + 1)))\n",
    "                    ans = max(ans, dp[i|(1 << j)])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        f = [0] * (1 << (numSlots * 2))\n",
    "        for i, fi in enumerate(f):\n",
    "            c = i.bit_count()\n",
    "            if c >= len(nums): continue\n",
    "            for j in range(numSlots * 2):\n",
    "                if (i & (1 << j)) == 0:  # 枚举空篮子 j\n",
    "                    s = i | (1 << j)\n",
    "                    f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c]))\n",
    "        return max(f)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        \"\"\"\n",
    "            - 最多 18 个数，每个数有放入/不放入篮子 2 种情况，总的状态数量 2^18\n",
    "            - 最多 9 个篮子，每个篮子可以放入 0/1/2 个数，总的状态数 3^9\n",
    "\n",
    "            (1) 用一个位数为 numSlots 的三进制 mask 表示当前篮子的状态。\n",
    "        \"\"\"\n",
    "\n",
    "        dp = [0] * (1 << (numSlots * 2))\n",
    "        for i, x in enumerate(dp):\n",
    "            cnt = i.bit_count()\n",
    "            if cnt >= len(nums): continue\n",
    "            for j in range(numSlots * 2):\n",
    "                if (i & (1 << j)) == 0:\n",
    "                    s = i | (1 << j)\n",
    "                    dp[s] = max(dp[s], x + ((j//2+1) & nums[cnt]))\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        f = [0] * (1 << (2 * numSlots))\n",
    "        for mask in range(1, len(f)):\n",
    "            c = bin(mask).count(\"1\")\n",
    "            if c > len(nums): \n",
    "                continue\n",
    "            for i in range(numSlots * 2):\n",
    "                if mask & (1 << i):\n",
    "                    f[mask] = max(f[mask], f[mask ^ (1 << i)] + (nums[c - 1] & (i // 2 + 1)))\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        f = [0] * (1 << numSlots * 2)\n",
    "        for i, fi in enumerate(f):\n",
    "            c = i.bit_count()\n",
    "            if c >= len(nums): continue\n",
    "            for j in range(numSlots * 2):\n",
    "                if (i & (1 << j)) == 0:\n",
    "                    s = i | (1 << j)\n",
    "                    f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c]))\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        tn=2*numSlots\n",
    "        n=len(nums)\n",
    "        dpls=[0 for i in range(1<<tn)]\n",
    "        max1=0\n",
    "        for i in range(1,1<<tn):\n",
    "            c=i.bit_count()\n",
    "            if c>n:\n",
    "                continue\n",
    "            for j in range(tn):\n",
    "                if (i>>j)&1==1:\n",
    "                    mask=i^(1<<j)\n",
    "                    dpls[i]=max(dpls[mask]+((j//2+1)&nums[c-1]),dpls[i])\n",
    "                    max1=max(max1,dpls[i])\n",
    "        return max1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        states = 1 << (numSlots * 2)\n",
    "        dp = [0 for _ in range(states)]\n",
    "\n",
    "        for state in range(states):\n",
    "            one_cnt = bin(state).count('1')\n",
    "            if one_cnt > len(nums):\n",
    "                continue\n",
    "            for i in range(numSlots * 2):\n",
    "                if (state >> i) & 1:\n",
    "                    dp[state] = max(dp[state], dp[state ^ (1 << i)] + ((i // 2 + 1) & nums[one_cnt - 1]))\n",
    "        \n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        f = [0] * (1 << (2*numSlots))\n",
    "        \n",
    "        for i, fi in enumerate(f):\n",
    "            c = i.bit_count()\n",
    "            if c >= len(nums):\n",
    "                continue\n",
    "            for j in range(2*numSlots):\n",
    "                if (i & (1 << j)) == 0:\n",
    "                    s = i | (1 << j)\n",
    "                    f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c]))\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = 2 * numSlots\n",
    "        f = [0] * (1 << n)\n",
    "        for i in range(1 << n):\n",
    "            cnt = i.bit_count()\n",
    "            if cnt >= len(nums): continue\n",
    "            for j in range(n):\n",
    "                if (i >> j & 1) == 0:\n",
    "                    f[i | 1 << j] = max(f[i | 1 << j], f[i] + ((j // 2 + 1) & nums[cnt]))\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        m = numSlots*2\n",
    "        ans=0\n",
    "        dp =[0]*(1<<m)\n",
    "        for mask in range(1<<m):\n",
    "            cnt = mask.bit_count()\n",
    "            if cnt>n:\n",
    "                continue\n",
    "            \n",
    "            for i in range(m):\n",
    "                if mask&(1<<i):\n",
    "                    dp[mask] =max(dp[mask],dp[mask^(1<<i)]+((nums[cnt-1])&(i//2+1)))\n",
    "            ans = max(ans,dp[mask])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        f = [0] * (1 << numSlots * 2)\n",
    "        \n",
    "\n",
    "        \n",
    "        for i, fi in enumerate(f):\n",
    "            c = i.bit_count()\n",
    "            if c >= len(nums): continue\n",
    "            for j in range(numSlots * 2):\n",
    "                if (i & (1 << j)) == 0:\n",
    "                    s = i | (1 << j)\n",
    "                    f[s] = max(f[s], fi + ((j // 2 + 1) & nums[c]))\n",
    "        return max(f)\n",
    "\n",
    "        n = len(nums)\n",
    "        x = (1 << n) - 1\n",
    "        while x < (1 << 2 * numSlots):\n",
    "            i, tmp = 0, 0\n",
    "            for j in range(2 * numSlots):\n",
    "                if x << j & 1:\n",
    "                    tmp += (j // 2 + 1) & nums[i]\n",
    "                    i += 1\n",
    "            res = max(res, tmp)\n",
    "            lb = x & - x\n",
    "            y = x + lb\n",
    "            x = (x ^ y) // lb >> 2 | y\n",
    "        return res\n",
    "\n",
    "        # x = (1 << k) - 1\n",
    "        # while x < (1 << n):\n",
    "        #     # 找到x中所有1的位数\n",
    "        #     path = [i + 1 for i in range(n) if x >> i & 1]\n",
    "        #     res.append(path)\n",
    "        #     lb = x & -x\n",
    "        #     y = x + lb\n",
    "        #     x = (x ^ y) // lb >> 2 | y\n",
    "        # return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        states = 1 << (numSlots * 2)\n",
    "        dp = [0 for _ in range(states)]\n",
    "\n",
    "        for state in range(states):\n",
    "            one_cnt = bin(state).count('1')\n",
    "            if one_cnt > len(nums):\n",
    "                continue\n",
    "            for i in range(numSlots * 2):\n",
    "                if (state >> i) & 1:\n",
    "                    dp[state] = max(dp[state], dp[state ^ (1 << i)] + ((i // 2 + 1) & nums[one_cnt - 1]))\n",
    "        \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# consider there are 2 * m slots, valued 1 ... m 1 ... m\r\n",
    "# problem is to distribute n nums into slots, and maximize AND sum\r\n",
    "# nPr(18, 18) > 1e15\r\n",
    "# dp[mask] := maximum AND sum to distribute first i integers in nums to bitset slots, i = bitset count\r\n",
    "# dp[mask] = max(dp[mask ^ (1 << j)] + (nums[i - 1] & val[j]))\r\n",
    "# O(2 * m * 2 ^ (2 * m)) < 1e7\r\n",
    "class Solution:\r\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        m2 = 2 * numSlots\r\n",
    "        hi = ((1 << n) - 1) << (m2 - n)\r\n",
    "        dp = [0] * (hi + 1)\r\n",
    "        res = 0\r\n",
    "\r\n",
    "        for mask in range(1, hi + 1):\r\n",
    "            i = bin(mask).count('1')\r\n",
    "            if i > n: continue\r\n",
    "            for j in range(m2):\r\n",
    "                if (mask >> j) & 1:\r\n",
    "                    dp[mask] = max(dp[mask], dp[mask ^ (1 << j)] + (nums[i - 1] & ((j % numSlots) + 1)))\r\n",
    "\r\n",
    "            if i == n: res = max(res, dp[mask])\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "    n = len(nums)\n",
    "    S = 3 ** numSlots\n",
    "    mask_bit = [[0] * numSlots for _ in range(S)]\n",
    "    for mask in range(S):\n",
    "      x = mask\n",
    "      for i in range(numSlots):\n",
    "        mask_bit[mask][i] = x % 3\n",
    "        x //= 3\n",
    "    dp = [-1 for _ in range(S)]\n",
    "    dp[0] = 0\n",
    "    for i in range(n):\n",
    "      new_dp = [-1 for _ in range(S)]\n",
    "      for mask in range(S):\n",
    "        if dp[mask] == -1:\n",
    "          continue\n",
    "        for j in range(numSlots):\n",
    "          if mask_bit[mask][j] == 2:\n",
    "            continue\n",
    "          new_mask = mask + 3 ** j\n",
    "          if new_dp[new_mask] == -1 or new_dp[new_mask] < dp[mask] + (nums[i] & (j + 1)):\n",
    "            new_dp[new_mask] = dp[mask] + (nums[i] & (j + 1))\n",
    "      dp = new_dp\n",
    "    return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # n = len(nums)\n",
    "        # u = (1 << n) - 1\n",
    "        # #用nums作为集合， iterate每个numSlot的index\n",
    "        # @cache\n",
    "        # def dfs(u, idx, cnt):\n",
    "        #     if cnt == 3:\n",
    "        #         return -inf\n",
    "        #     if idx == numSlots:\n",
    "        #         return 0 if u == 0 and cnt == 0 else -inf\n",
    "        #     cur = dfs(u, idx + 1, 0)\n",
    "        #     for i in range(n):\n",
    "        #         if (u >> i) & 1:\n",
    "        #             cur = max(cur, (nums[i] & (idx + 1)) + dfs(u ^ (1 << i), idx, cnt + 1), \n",
    "        #             (nums[i] & (idx + 1)) + dfs(u ^ (1 << i), idx + 1, 1))\n",
    "        #     return cur\n",
    "        # return dfs(u, 0, 0)\n",
    "\n",
    "        #反过来， 用slots作为集合， iterate每个num放哪里\n",
    "        # @cache\n",
    "        # def dfs(u, idx):\n",
    "        #     if idx == len(nums):\n",
    "        #         return 0\n",
    "        #     mask = u\n",
    "        #     ans = -inf\n",
    "        #     for i in range(numSlots):\n",
    "        #         if mask % 3 >= 1:\n",
    "        #             ans = max(ans, dfs(u - 3 ** i, idx + 1) + (nums[idx] & (i + 1)))\n",
    "        #         mask //= 3\n",
    "        #     return ans\n",
    "        # return dfs(u, 0)\n",
    "        u = 3 ** numSlots\n",
    "        n = len(nums)\n",
    "        dp = [[0] * (n + 1) for _ in range(u)]\n",
    "        #状态\n",
    "        for i in range(u):\n",
    "            mask = i\n",
    "            for k in range(numSlots):\n",
    "                if mask % 3 < 2:\n",
    "                    for j in range(n):\n",
    "                        dp[i + (3 ** k)][j + 1] = max(dp[i + (3 ** k)][j + 1], dp[i][j] + (nums[j] & (k + 1)))\n",
    "                mask //= 3\n",
    "        ans = 0\n",
    "        for i in range(u):\n",
    "            ans = max(ans, dp[i][n])\n",
    "        return ans\n",
    "            \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, state):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            \n",
    "            state = list(state)\n",
    "            res = 0\n",
    "            for i in range(numSlots):\n",
    "                if state[i] < 2:\n",
    "                    state[i] += 1\n",
    "                    res = max(res, (nums[idx] & (i + 1)) + dfs(idx + 1, tuple(state)))\n",
    "                    state[i] -= 1\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, tuple([0] * numSlots))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, a: List[int], b: int) -> int:\n",
    "        n = len(a)\n",
    "        m = b\n",
    "        @cache\n",
    "        def f(x):\n",
    "            t = list(x)\n",
    "            use = 0 \n",
    "            for j in range(m):\n",
    "                use += t[j] \n",
    "            if use==n:\n",
    "                return 0 \n",
    "            j = use \n",
    "            ans = -float('inf')\n",
    "            for i in range(m):\n",
    "                if t[i]<2:\n",
    "                    tmp = t[::] \n",
    "                    tmp[i] += 1 \n",
    "                    ans = max(ans, f(tuple(tmp)) + ((i+1) & a[j]) ) \n",
    "            # print(x, ans)\n",
    "            return ans \n",
    "        return f((0 for j in range(m)))\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def f(i, state):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            tmp = list(state)\n",
    "            res = 0\n",
    "            for j in range(numSlots):\n",
    "                if tmp[j] < 2:\n",
    "                    tmp[j] += 1\n",
    "                    res = max(res, ((j + 1) & nums[i]) + f(i + 1, tuple(tmp)))\n",
    "                    tmp[j] -= 1\n",
    "            return res \n",
    "        \n",
    "        return f(0, tuple([0] * numSlots))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "\n",
    "        n=len(nums)\n",
    "        mask=3**numSlots-1\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur,mask):\n",
    "            if cur==n:                \n",
    "                return 0\n",
    "            ans=0\n",
    "            for i in range(numSlots):\n",
    "                # print(mask//3**(i-1))\n",
    "                if mask//3**i%3:\n",
    "                    ans=max(ans,(nums[cur]&(i+1))+dfs(cur+1,mask-3**i))\n",
    "                    \n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,mask)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "\n",
    "        cnt=[2]*numSlots\n",
    "        n=len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur,cnt):\n",
    "            cnt=list(cnt)\n",
    "            if cur==n:                \n",
    "                return 0\n",
    "\n",
    "            ans=0\n",
    "            for i in range(numSlots):\n",
    "                if cnt[i]:\n",
    "                    cnt[i]-=1\n",
    "                    ans=max(ans,(nums[cur]&(i+1))+dfs(cur+1,tuple(cnt)))\n",
    "                    cnt[i]+=1\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,tuple(cnt))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # 1 <= numSlots <= 9 ;; 1 <= n <= 2 * numSlots ;; 1 <= nums[i] <= 15\n",
    "        # 数据范围比较小，可能是暴力相关的\n",
    "        #  与和 定义为每个数与它所在篮子编号的 按位与运算 结果之和\n",
    "        \n",
    "        @cache\n",
    "        def f(i, s):\n",
    "            if i >= len(nums):\n",
    "                return 0\n",
    "            s = list(s)\n",
    "            ans = 0\n",
    "            for j in range(numSlots):\n",
    "                if s[j] < 2:\n",
    "                    s[j] += 1\n",
    "                    ans = max(ans, (nums[i] & ( j+1)) + f(i+1, tuple(s)))\n",
    "                    s[j] -= 1\n",
    "            return ans\n",
    "        \n",
    "        return f(0, tuple(0 for _ in range(numSlots)))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        lnums = len(nums)\n",
    "        @cache\n",
    "        def dfs(idx, status):\n",
    "            if idx == lnums:\n",
    "                return 0\n",
    "            ret = 0\n",
    "            for i in range(numSlots):\n",
    "                s = (status & (3 << 2 * i)) >> 2 * i\n",
    "                if s <= 1:\n",
    "                    ret = max(ret, dfs(idx + 1, status + (1 << 2 * i)) + (nums[idx] & (i + 1)))\n",
    "            return ret\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i,st):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            st,ans = list(st),0\n",
    "            for j,x in enumerate(st):\n",
    "                if x < 2:\n",
    "                    st[j] += 1\n",
    "                    ans = max(ans,dfs(i + 1,tuple(st)) + (nums[i] & (j + 1)))\n",
    "                    st[j] -= 1\n",
    "            return ans\n",
    "\n",
    "\n",
    "        return dfs(0,tuple([0]*numSlots))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, state):\n",
    "            if idx == len(nums):\n",
    "                return 0\n",
    "            st, res = list(state), 0\n",
    "            for i, s in enumerate(state):\n",
    "                if s > 0:\n",
    "                    st[i] -= 1\n",
    "                    res = max(res, dfs(idx + 1, tuple(st)) + ((i + 1) & nums[idx]))\n",
    "                    st[i] += 1\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, tuple([2] * numSlots))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # n = len(nums)\n",
    "        # u = (1 << n) - 1\n",
    "        # #用nums作为集合， iterate每个numSlot的index\n",
    "        # @cache\n",
    "        # def dfs(u, idx, cnt):\n",
    "        #     if cnt == 3:\n",
    "        #         return -inf\n",
    "        #     if idx == numSlots:\n",
    "        #         return 0 if u == 0 and cnt == 0 else -inf\n",
    "        #     cur = dfs(u, idx + 1, 0)\n",
    "        #     for i in range(n):\n",
    "        #         if (u >> i) & 1:\n",
    "        #             cur = max(cur, (nums[i] & (idx + 1)) + dfs(u ^ (1 << i), idx, cnt + 1), \n",
    "        #             (nums[i] & (idx + 1)) + dfs(u ^ (1 << i), idx + 1, 1))\n",
    "        #     return cur\n",
    "        # return dfs(u, 0, 0)\n",
    "\n",
    "        #反过来， 用slots作为集合， iterate每个num放哪里\n",
    "        u = 3 ** numSlots - 1\n",
    "        @cache\n",
    "        def dfs(u, idx):\n",
    "            if idx == len(nums):\n",
    "                return 0\n",
    "            mask = u\n",
    "            ans = -inf\n",
    "            for i in range(numSlots):\n",
    "                if mask % 3 >= 1:\n",
    "                    ans = max(ans, dfs(u - 3 ** i, idx + 1) + (nums[idx] & (i + 1)))\n",
    "                mask //= 3\n",
    "            return ans\n",
    "        return dfs(u, 0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, state):\n",
    "            if idx == len(nums):\n",
    "                return 0\n",
    "            st, res = list(state), 0\n",
    "            for i, s in enumerate(state):\n",
    "                if s < 2:\n",
    "                    st[i] += 1\n",
    "                    res = max(res, dfs(idx + 1, tuple(st)) + ((i + 1) & nums[idx]))\n",
    "                    st[i] -= 1\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, tuple([0] * numSlots))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, state):\n",
    "            if idx == len(nums):\n",
    "                return 0\n",
    "            st, res = list(state), 0\n",
    "            for i, s in enumerate(state):\n",
    "                if s < 2:\n",
    "                    st[i] += 1\n",
    "                    res = max(res, dfs(idx + 1, tuple(st)) + ((i + 1) & nums[idx]))\n",
    "                    st[i] -= 1\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, tuple([0] * numSlots))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(idx, mask):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            tmp = list(mask)\n",
    "            for j in range(numSlots):\n",
    "                if tmp[j] < 2:\n",
    "                    c = tmp[:]\n",
    "                    c[j] += 1\n",
    "                    res = max(res, dfs(idx + 1, tuple(c)) + (nums[idx] & (j + 1)))\n",
    "            return res\n",
    "\n",
    "        a = [0] * numSlots\n",
    "        return dfs(0, tuple(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(idx, mask):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            tmp = list(mask)\n",
    "            for j in range(numSlots):\n",
    "                if tmp[j] < 2:\n",
    "                    c = tmp[:]\n",
    "                    c[j] += 1\n",
    "                    res = max(res, dfs(idx + 1, tuple(c)) + (nums[idx] & (j + 1)))\n",
    "            return res\n",
    "\n",
    "        a = [0] * numSlots\n",
    "        return dfs(0, tuple(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def f(i, a, b):     # a, b == a|b, a&b\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            ans, v = 0, nums[i]\n",
    "            for k in range(1, numSlots+1):\n",
    "                if b & (1 << k) == 0:\n",
    "                    x = b | (1 << k)\n",
    "                    ans = max(ans, (v & k) + f(i-1, a|x, a&x))\n",
    "            return ans\n",
    "        \n",
    "        return f(n-1, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def f(i, a, b):     # a, b == a|b, a&b  (three states: 00, 10, 11)\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for k in range(1, numSlots+1):\n",
    "                if b & (1 << k) == 0:\n",
    "                    x = b | (1 << k)\n",
    "                    ans = max(ans, (nums[i] & k) + f(i-1, a|x, a&x))\n",
    "            return ans\n",
    "        \n",
    "        return f(n-1, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        maskMap = [[1<<x, (x>>1)+1] for x in range(numSlots*2)]\n",
    "        masks, masks1 = defaultdict(int), defaultdict(int)\n",
    "        masks[0] = 0\n",
    "        for n in nums:\n",
    "            masks1.clear()\n",
    "            for mask, val in masks.items():\n",
    "                for m, slot in maskMap:\n",
    "                    if m & mask == 0:\n",
    "                        m |= mask\n",
    "                        masks1[m] = max(masks1[m], val + (n & slot))\n",
    "            masks, masks1 = masks1, masks\n",
    "        return max(masks.values())\n",
    "\n",
    "\n",
    "        # R[k][m] = max(R[k-1][subm] + )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        maskMap = {(1<<x): (x>>1)+1 for x in range(numSlots*2)}\n",
    "        masks, masks1 = defaultdict(int), defaultdict(int)\n",
    "        masks[0] = 0\n",
    "        for n in nums:\n",
    "            masks1.clear()\n",
    "            for mask, val in masks.items():\n",
    "                for m, slot in maskMap.items():\n",
    "                    if m & mask == 0:\n",
    "                        m |= mask\n",
    "                        masks1[m] = max(masks1[m], val + (n & slot))\n",
    "            masks, masks1 = masks1, masks\n",
    "        return max(masks.values())\n",
    "\n",
    "\n",
    "        # R[k][m] = max(R[k-1][subm] + )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        baskets = \"\"\n",
    "        for i in range(numSlots):\n",
    "            baskets+=\"0\"\n",
    "        @cache\n",
    "        def func1(baskets, pos):\n",
    "            if pos == n - 1:\n",
    "                res = 0\n",
    "                for i in range(numSlots):\n",
    "                    v=int(baskets[i])\n",
    "                    if v == 2:\n",
    "                        continue\n",
    "                    res = max(res, ((i + 1) & nums[pos]))\n",
    "                return res\n",
    "            res = 0\n",
    "            for i in range(numSlots):\n",
    "                v = int(baskets[i])\n",
    "                if v == 2:\n",
    "                    continue\n",
    "                copy_bas = baskets[:i]+str(v+1)+baskets[i+1:]\n",
    "                res = max(res, ((i + 1) & nums[pos]) + func1(copy_bas, pos + 1))\n",
    "            return res\n",
    "        return func1(baskets, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        baskets = \"\"\n",
    "        for i in range(numSlots):\n",
    "            baskets+=\"0\"\n",
    "        @cache\n",
    "        def func1(baskets, pos):\n",
    "            if pos == n - 1:\n",
    "                res = 0\n",
    "                for i in range(numSlots):\n",
    "                    v=int(baskets[i])\n",
    "                    if v == 2:\n",
    "                        continue\n",
    "                    res = max(res, ((i + 1) & nums[pos]))\n",
    "                return res\n",
    "            res = 0\n",
    "            for i in range(numSlots):\n",
    "                v = int(baskets[i])\n",
    "                if v == 2:\n",
    "                    continue\n",
    "                copy_bas = baskets[:i]+str(v+1)+baskets[i+1:]\n",
    "                res = max(res, ((i + 1) & nums[pos]) + func1(copy_bas, pos + 1))\n",
    "            return res\n",
    "\n",
    "        a = func1(baskets, 0)\n",
    "        print(a)\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        n = len(nums)\n",
    "        baskets = \"\"\n",
    "        for i in range(numSlots):\n",
    "            baskets+=\"0\"\n",
    "        @cache\n",
    "        def func1(baskets, pos):\n",
    "            if pos == n - 1:\n",
    "                res = 0\n",
    "                for i in range(numSlots):\n",
    "                    v=int(baskets[i])\n",
    "                    if v == 2:\n",
    "                        continue\n",
    "                    res = max(res, ((i + 1) & nums[pos]))\n",
    "                return res\n",
    "            res = 0\n",
    "            for i in range(numSlots):\n",
    "                v = int(baskets[i])\n",
    "                if v == 2:\n",
    "                    continue\n",
    "                copy_bas = baskets[:i]+str(v+1)+baskets[i+1:]\n",
    "                res = max(res, ((i + 1) & nums[pos]) + func1(copy_bas, pos + 1))\n",
    "            return res\n",
    "        return func1(baskets, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "from scipy.optimize import linear_sum_assignment\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], ns: int) -> int:\n",
    "        nums, slots, mx = nums + [0] * (2 * ns - len(nums)), [*range(1, ns + 1)] * 2, np.zeros((ns * 2, ns * 2))\n",
    "        for (i, x), (j, sn) in product(enumerate(nums), enumerate(slots)): mx[i, j] = x & sn\n",
    "        return int(mx[linear_sum_assignment(-mx)].sum())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        #篮子个数最多9个\n",
    "        #数的范围并不算大\n",
    "        #启发式：对于第i个篮子，选择不放，选择放1个，选择放两个\n",
    "        #原问题，前i个篮子，将集合S分配能得到的最大与和\n",
    "        #子问题，前i-1个篮子，将集合S'分配能得到的最大与和\n",
    "        #状态个数n*2^(n),单个状态计算时间的加和？2^n+1\n",
    "\n",
    "        #怎么样才能更快地做出选择呢？\n",
    "        #n*n*2^n*3\n",
    "        #还是太慢了。。。\n",
    "\n",
    "        '''\n",
    "        观察盒子的比不过观察球的\n",
    "        为什么？\n",
    "        仔细分析发现，观察球的话你可以少记录一个状态，这是很好的\n",
    "        启发式：我们可以看成有2*ns个盒子，这样就方便很多了.每个盒子都必须被放入一个数字\n",
    "        '''\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def dfs(s:int):\n",
    "            i=s.bit_count()\n",
    "            if i==n:\n",
    "                return 0\n",
    "            #当前应该枚举到第i个数字,但是有些篮子可以不放入数字，那就没办法反向枚举了。。\n",
    "            res=-inf\n",
    "            for j in range(2*numSlots):\n",
    "                if s>>j & 1==0:\n",
    "                    res=max(res,dfs(s|(1<<j))+(nums[i-1]&(j+2)//2))\n",
    "            return res\n",
    "        return dfs(0)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            idx = s.bit_count()\n",
    "            if idx >= n:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for i in range(2 * m):\n",
    "                if (s >> i) & 1 == 0:\n",
    "                    j = s | (1 << i)\n",
    "                    ans = max(ans, ((i // 2 + 1) & nums[idx]) + dfs(j))\n",
    "            return ans\n",
    "\n",
    "        n = len(nums)\n",
    "        m = numSlots \n",
    "        return dfs(0)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # 观察数据量 --- 发现数据量总体比较小 ----- 考虑暴力 ---- 看看能不能用DP\n",
    "        # 我们可以稍微改变一下：\n",
    "        # 把每个篮子放两个，改成 2 * n 个篮子，每个篮子放一个 ------ 就能减少一个参数的传入，优化时间\n",
    "        # 篮子的总数量最大是 18 那么我们可以用二进制去枚举 1 表示 该篮子被占用了， 0 表示该篮子没有被占用\n",
    "        # 每个 f[i] 就表示 nums前 i 个数 的集合在此时最大的情况\n",
    "        # 从提示可以看出 n 的数量可能小于 2 * numSlots ----- 会有篮子多的情况\n",
    "        # 转移方程\n",
    "        # f[i + 2 ** j] --(表示下一位) = max(f[i + 2 ** j], f[i] + nums[j] AND (j // 2 + 1))\n",
    "\n",
    "        # dp\n",
    "        n = len(nums)\n",
    "        m = numSlots * 2\n",
    "        @ cache\n",
    "        def dfs(i:int, j):\n",
    "            res = 0\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            for p in range(m):\n",
    "                if j & 1 << p == 0:   # 表示空篮子\n",
    "                    res = max(res, dfs(i-1, j | 1 << p) + (nums[i] & (p // 2 + 1)))\n",
    "            return res\n",
    "        return dfs(n-1, 0)\n",
    "\n",
    "        # 从递归到递推\n",
    "        # n = len(nums)\n",
    "        # m = numSlots * 2\n",
    "        # dp = [[0] * m for _ in range(n + 1)] \n",
    "        # for i, v in enumerate(nums):\n",
    "        #     for p in range(m):\n",
    "        #         if dp[i][p] == 0:   # 表示空篮子\n",
    "        #             dp[i][p] = max(dp[i][p], dp[i-1][])\n",
    "\n",
    "        # 状态压缩\n",
    "\n",
    "    \n",
    "    \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        # 观察数据量 --- 发现数据量总体比较小 ----- 考虑暴力 ---- 看看能不能用DP\n",
    "        # 我们可以稍微改变一下：\n",
    "        # 把每个篮子放两个，改成 2 * n 个篮子，每个篮子放一个 ------ 就能减少一个参数的传入，优化时间\n",
    "        # 篮子的总数量最大是 18 那么我们可以用二进制去枚举 1 表示 该篮子被占用了， 0 表示该篮子没有被占用\n",
    "        # 每个 f[i] 就表示 nums前 i 个数 的集合在此时最大的情况\n",
    "        # 从提示可以看出 n 的数量可能小于 2 * numSlots ----- 会有篮子多的情况\n",
    "        # 转移方程\n",
    "        # f[i + 2 ** j] --(表示下一位) = max(f[i + 2 ** j], f[i] + nums[j] AND (j // 2 + 1))\n",
    "\n",
    "        # dp\n",
    "        n = len(nums)\n",
    "        m = numSlots * 2\n",
    "        @ cache\n",
    "        def dfs(i:int, j):\n",
    "            res = 0\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            for p in range(m):\n",
    "                if j & 1 << p == 0:   # 表示空篮子\n",
    "                    res = max(res, dfs(i+1, j | 1 << p) + (nums[i] & (p // 2 + 1)))\n",
    "            return res\n",
    "        return dfs(0, 0)\n",
    "\n",
    "        # 状态压缩\n",
    "\n",
    "    \n",
    "    \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "        u = (1 << (2 * numSlots)) - 1\n",
    "        n = len(nums)\n",
    "        m = 2 * numSlots\n",
    "        @cache\n",
    "        def dfs(mask, i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for j in range(m):\n",
    "                if mask >> j & 1:\n",
    "                    res = max(res, dfs(mask ^ (1 << j), i + 1) + ((j // 2 + 1) & nums[i]))\n",
    "            return res\n",
    "        return dfs(u, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:\n",
    "\n",
    "        n=len(nums)\n",
    "        mask=2**(2*numSlots)-1\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur,mask):\n",
    "            if cur==n:                \n",
    "                return 0\n",
    "            ans=0\n",
    "            for i in range(2*numSlots):\n",
    "                if mask&(1<<i):\n",
    "                    ans=max(ans,(nums[cur]&((i+2)//2))+dfs(cur+1,mask-(1<<i)))\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,mask)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
